#include <iostream>


struct ListNode
{
    int val = 0;
    ListNode* next = nullptr;
    ListNode(int val, ListNode* next) :val(val), next(next) {}
};

// class Solution {
// public:
//     ListNode* removeNthFromEnd(ListNode* head, int n) {
//         ListNode* slow = head;
//         ListNode* fast = head;

//         //slow移动到待删除节点的前一个位置
//         n++;
//         bool head_flag = false;
//         while(n--)
//         {
//             if(fast != nullptr)
//                 fast = fast->next;
//             else
//                 head_flag = true;
//         }

//         while(fast)
//         {
//             slow = slow->next;
//             fast = fast->next;
//         }

//         //是否为头删
//         ListNode* cur = nullptr;
//         if(head_flag)
//         {
//             cur = head;
//             head = head->next;
//         }
//         else
//         {
//             cur = slow->next;
//             ListNode* next = cur->next;
//             slow->next = next;
//         }
//         cur->next = nullptr;
//         delete cur;

//         return head;
//     }
// };

// class Solution
// {
// public:
//     ListNode* removeNthFromEnd(ListNode* head, int n)
//     {
//         //添加一个节点，这样就不需要判断是不是要删除头节点了
//         ListNode* empty_node = new ListNode();
//         empty_node->next = head;

//         ListNode* slow = empty_node;
//         ListNode* fast = empty_node;

//         //找到待删除节点的前一个位置
//         n++;
//         while(n--)
//         {
//             fast = fast->next;
//         }
//         while(fast)
//         {
//             fast = fast->next;
//             slow = slow->next;
//         }


//         //删除
//         ListNode* delete_node = slow->next;
//         slow->next = delete_node->next;

//         delete_node->next = nullptr;
//         delete delete_node;
//         head = empty_node->next;
//         empty_node->next = nullptr;
//         delete empty_node;

//         return head;
//     }
// };

class Solution
{
public:
    ListNode* removeNthFromEnd(ListNode* head, int n)
    {
        ListNode* dummy = new ListNode(0, head);
        ListNode* fast = head;
        ListNode* slow = dummy;

        //找到待删除节点的前一个位置
        for(int i = 0; i < n; i++)
            fast = fast->next;
        while(fast)
        {
            slow = slow->next;
            fast = fast->next;
        }
        ListNode* cur = slow->next;
        slow->next = cur->next;
        delete cur;

        return dummy->next;
    }
};